package com.wcj.array;

/**
 * 给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。
 *
 * 不占用额外内存空间能否做到？
 * 给定 matrix =
 * [
 *   [1,2,3],
 *   [4,5,6],
 *   [7,8,9]
 * ],
 *
 * 原地旋转输入矩阵，使其变为:
 * [
 *   [7,4,1],
 *   [8,5,2],
 *   [9,6,3]
 * ]
 *
 * 重要公式：
 * matrix[row][col] 旋转九十度，行和列的变换
 * 行从零开始
 * row = col
 * col = n - row - 1
 */
public class 旋转矩阵 {


    /**
     * 思路，根据以上公式，能找出matric[row][col]旋转九十度后为matric[col][n-row-1]
     *                    对应的matric[col][n-row-1]旋转九十度带入公式得matrix[n-row-1][n-col-1]
     *                    对应的matrix[n-row-1][n-col-1]旋转九十度带入公式得matric[n-col-1][row]
     *                    对应的matric[n-col-1][row]旋转九十度即回到原点
     *                    要从后往前覆盖值，即我们需要存储第一个元素
     *  另外对于n为偶数，我们需要执行操作的元素为 (n/2)(n/2) 分别对应行和列
     *      对应n为奇数，我们需要执行操作的元素为 ((n-1)/2)*((n+1)/2)
     *      对于行 n/2 和 n-1/2  可以合并为n/2 因为对于奇数整型，小数会省略
     *      对于列 n/2 和 n+1/2  可以合并为n+1/2 因为对于偶数再加一，除二后相等
     * @param matrix
     */
    public  void rotate(int[][] matrix){
        int len = matrix.length;
        for (int i = 0; i < len/2; i++){
            for (int j = 0; j < (len + 1)/2;j++){
                int temp = matrix[i][j];
                matrix[i][j] = matrix[len-j-1][i];
                matrix[len-j-1][i] = matrix[len-i-1][len-j-1];
                matrix[len-i-1][len-j-1] = matrix[j][len-i-1];
                matrix[j][len-i-1] = temp;
            }
        }
    }
}
